\subsection{Matching in bipartite graphs}
\begin{definition}
	Let \( G = (X \sqcup Y, E) \) be a bipartite graph.
	A \emph{matching from \( X \) to \( Y \)} is a set of edges \( E' \subseteq \qty{xy_x \mid x \in X, y_x \in Y} = E \) such that the map \( x \mapsto y_x \) is injective.
\end{definition}
\begin{definition}
	Let \( G \) be a graph, \( A \subseteq V(G) \).
	We define \( N_G(A) = \qty{\bigcup_{x \in A} N(x)} \).
\end{definition}
\begin{theorem}[Hall]
	Let \( G = (X \sqcup Y, E) \) be a bipartite graph.
	There exists a matching from \( X \) to \( Y \) if and only if \emph{Hall's criterion} holds: that \( \abs{A} \leq \abs{N(A)} \) for all \( A \subseteq X \).
\end{theorem}
\begin{proof}
	The forward direction is simple, by considering the image of the injective map \( x \mapsto y_x : A \to N(A) \) for each subset \( A \subseteq X \).
	Conversely, suppose Hall's criterion is satisfied.
	We apply induction on \( \abs{X} \).
	If \( \abs{X} = 1 \), \( N(X) \) is nonempty and so the proof is complete.

	If there does not exist \( \varnothing \neq A \subsetneq X \) such that \( \abs{N(A)} = \abs{A} \), we have \( \abs{A} < \abs{N(A)} \) for all \( \varnothing \neq A \neq X \).
	Let \( xy \in E \), and let \( G' = G[X \setminus \qty{x} \sqcup Y \setminus \qty{y}] \).
	By induction, it suffices to show Hall's criterion holds for \( G' \).
	If \( B \subseteq X \setminus \qty{x} \), we have
	\[ \abs{N_{G'}(B)} \geq \abs{N_G(B)} - 1 \geq \abs{B} \]
	as required.

	However, suppose there exists such a set \( \varnothing \neq A \subsetneq X \) with \( \abs{A} = \abs{N(A)} \).
	Let \( G_1 = G[A \sqcup N(A)] \) and \( G_2 = G[X \setminus A \sqcup Y \setminus N(A)] \).
	\( G_1 \) satisfies Hall's criterion.
	Indeed, for \( B \subseteq A \), \( N_{G_1}(B) = N_G(B) \) as required.
	\( G_2 \) also satisfies Hall's criterion.
	Suppose \( B \subseteq X \setminus A \), and consider \( N_G(A \cup B) \).
	We have
	\[ \abs{A} + \abs{B} \leq \abs{N_G(A \cup B)} = \abs{N_G(A)} + \abs{N_{G_2}(B)} \implies \abs{B} \leq \abs{N_{G_2}(B)} \]
	Hence Hall's criterion is satisfied.

	Then by induction on \( G_1 \) and \( G_2 \), the proof is complete.
\end{proof}
\begin{definition}
	A \emph{matching of deficiency \( d \) from \( X \) to \( Y \)} is a matching from \( X' \subseteq X \) to \( Y \) where \( \abs{X'} + d = \abs{X} \).
\end{definition}
\begin{theorem}[defect Hall]
	Let \( G = (X \sqcup Y, E) \) be a bipartite graph.
	\( G \) contains a matching of deficiency \( d \leq \abs{X} \) if and only if \( \abs{A} \leq \abs{N(A)} + d \) for all \( A \subseteq X \).
\end{theorem}
\begin{proof}
	The forward direction is again a simple proof.
	Let \( G = (X \sqcup Y, E) \) be a graph such that \( \abs{A} \leq \abs{N(A)} + d \) for all \( A \subseteq X \).
	Let \( G' = (X \sqcup (Y \cup \qty{z_1, \dots, z_d}), E \cup E') \) where \( E' = \qty{xz_i \mid x \in X, i \in \qty{1, \dots, d}} \).
	Hall's criterion on \( G' \) is satisfied, so there exists a matching.
	Deleting these new vertices \( \qty{z_1, \dots, z_d} \) and the edge set \( E' \), we construct a matching from \( X \) to \( Y \) of deficiency at most \( d \).
	To construct a matching of deficiency precisely \( d \), we can delete extra edges as required.
\end{proof}
\begin{definition}
	The \emph{maximum degree} \( \Delta(G) \) (resp.\ \emph{minimum degree} \( \delta(G) \)) of a graph \( G \) is the maximum (resp.\ minimum) degree of a vertex in \( G \).
\end{definition}
\begin{definition}
	A graph is \emph{regular} if all vertices have the same degree, or equivalently, \( \delta(G) = \Delta(G) \).
	A graph is \emph{\( k \)-regular} if \( \delta(G) = \Delta(G) = k \).
\end{definition}
\begin{corollary}
	Let \( G = (X \sqcup Y, E) \) be a \( k \)-regular bipartite graph and \( k \geq 1 \).
	Then there exists a matching from \( X \) to \( Y \).
\end{corollary}
\begin{proof}
	It suffices to show Hall's criterion holds.
	Let \( A \subseteq X \).
	Then
	\[ e(G[A \cup N(A)]) = \sum_{x \in A} \deg x = k \abs{A};\quad e(G[A \cup N(A)]) = \sum_{x \in N(A)} \deg v \leq k \abs{N(A)} \]
	Hence \( \abs{A} \leq \abs{N(A)} \).
\end{proof}
\begin{example}
	Let \( \Gamma \) be a finite group, and let \( H \leq \Gamma \).
	Let \( L_1, \dots, L_n \) be the left cosets, and \( R_1, \dots, R_n \) be the right cosets.
	We want to find \( g_1, \dots, g_n \) such that \( g_1 H, \dots, g_n H \) are the left cosets and \( H g_1, \dots, H g_n \) are the right cosets.

	Consider the graph \( G = (\qty{L_1, \dots, L_n} \sqcup \qty{R_1, \dots, R_n}, E) \) where an edge lies between \( L_i \) and \( R_j \) if \( L_i \cap R_j \neq \varnothing \).
	It suffices to find a matching in this graph, because then each edge in the matching implies the existence of a representative for both cosets.
	Let \( A \subseteq \qty{L_1, \dots, L_n} \), so \( A = \qty{L_{i_1}, \dots, L_{i,k}} \).
	Consider \( \abs{\bigcup_{j=1}^k L_{ij}} = k \abs{H} \), but since \( R_1, \dots, R_n \) partition \( \Gamma \) and have size \( \abs{H} \), at least \( k \) right cosets of \( H \) must intersect \( \bigcup R_{ij} \).
	Hence Hall's criterion is satisfied.
\end{example}

\subsection{Connectivity}
Let \( S \subseteq V(G) \).
Then we define \( G - S = G[V(G) \setminus S] \).
\begin{definition}
	Let \( G \) be a graph, and \( \abs{G} \geq 1 \).
	Then we define the \emph{connectivity parameter} \( \kappa \) of \( G \) by
	\[ \kappa = \min\qty{\abs{S} \mid S \subseteq V(G), G - S \text{ is disconnected or a single vertex}} \]
	We say that \( G \) is \( k \)-connected if \( k \leq \kappa \).
	Hence \( G \) is \( k \)-connected if and only if for all sets \( S \) of at most \( k-1 \) vertices, \( G - S \) is connected and not a single vertex.
\end{definition}
\begin{example}
	\( \kappa(\text{Petersen graph}) = 3 \), because deleting any two vertices leaves the graph connected, but deleting the neighbourhood of any vertex disconnects the graph.
	\( \kappa(G) = 1 \) if \( G \) is a tree.
	\( \kappa(C_n) = 2 \) for \( n \geq 3 \).
	\( \kappa(K_n) = n - 1 \).
\end{example}
\begin{definition}
	Let \( G \) be a graph, and \( a, b \in V(G) \).
	We say that the \( a \)--\( b \) paths \( P_1, \dots, P_k \) are \emph{disjoint} if \( P_i \cap P_j = \qty{a, b} \) for \( i \neq j \).
\end{definition}
Note that \( \delta(G) \geq \kappa(G) \).
This follows because removing the neighbours of the vertex of minimum degree disconnects the graph or leaves it a single vertex.
Also, we can easily see that \( \kappa(G - x) \geq \kappa(G) - 1 \).
Note that we can have \( \kappa(G-x) > \kappa(G) \) by considering a \( 2 \)-connected graph with an additional leaf.
\begin{definition}
	Let \( G \) be a graph and \( a \neq b \in V(G) \), where \( a \not\sim b \).
	We say that \( S \subseteq V(G) \setminus \qty{a,b} \) is a \emph{\( a \)--\( b \) separator} if \( G - S \) disconnects \( a \) and \( b \).
\end{definition}
\begin{theorem}[Menger, form 1]
	Let \( G \) be a connected graph and \( a \neq b \in V(G) \), where \( a \not\sim b \).
	The minimum size of an \( a \)--\( b \) separator is the maximum number of disjoint paths from \( a \) to \( b \).
	Equivalently, if all \( a \)--\( b \) separators have size at least \( k \), then there exist \( k \) disjoint \( a \)--\( b \) paths.
\end{theorem}
\begin{proof}
	We write \( \kappa_{a,b}(G) \) for the minimum size of an \( a \)--\( b \) separator.
	Note that \( \kappa(G - x) \geq \kappa(G) - 1 \), and \( \kappa(G - xy) \geq \kappa(G) - 1 \).
	We also have the same properties for \( \kappa_{a,b} \).

	Suppose the theorem does not hold, then there is a nonempty set of counterexamples.
	Let \( \mathcal G \) be the set of counterexamples of smallest possible \( k \), and let \( G \) be an element of \( \mathcal G \) with the smallest possible amount of edges.
	Let \( S \) be a minimal \( a \)--\( b \) separator in \( G \), so \( \abs{S} = k \).
	Note that the theorem is true for \( k = 1 \), so we may assume \( k \geq 2 \).

	If \( S \neq N(a) \) and \( S \neq N(b) \), consider \( G - S \).
	Then \( a, b \) lie in different connected components.
	Let \( A \) be the component containing \( a \), and \( B \) be the component containing \( b \).
	Define \( G_a \) to be the graph \( G[A \cup S] \) together with a vertex \( c \) with edges to each \( s \in S \).
	Similarly, define \( G_b \) to be the graph \( G[B \cup S] \) together with a vertex \( c \) with edges to each \( s \in S \).

	Note that \( \kappa_{a,c}(G_a) \geq k \), because any \( a \)--\( c \) separator in \( G_a \) is an \( a \)--\( b \) separator in \( G \), and \( \kappa_{b,c}(G_b) \geq k \) by symmetry.
	Note further that \( e(G_a), e(G_b) < e(G) \); because \( S \neq N(a) \) and \( S \neq N(b) \), the amount of newly added edges is smaller than the amount of edges that must have been removed in each induced graph.
	Then by minimality of \( G \), the \( G_a \) and \( G_b \) are not counterexamples to the theorem.
	Hence there exist disjoint \( a \)--\( c \) paths \( P_1, \dots, P_k \) in \( G_a \) and disjoint \( c \)--\( b \) paths \( Q_1, \dots, Q_k \) in \( G_b \).
	Concatenating \( P_i \) with \( Q_i \), we obtain \( k \) disjoint \( a \)--\( b \) paths in \( G \).
	Then \( G \) is not a counterexample.

	Now, suppose \( S = N(a) \) without loss of generality.
	We claim that \( N(a) \cap N(b) = \varnothing \).
	If there exists \( x \in N(a) \cap N(b) \), then consider the graph \( G - x \).
	We have \( \kappa_{a,b}(G - x) \geq k - 1 \), so by minimality, there exist disjoint \( a \)--\( b \) paths \( P_1, \dots, P_{k-1} \) in \( G - x \).
	Adding the path \( a, x, b \), which is disjoint from all others, we obtain \( k \) disjoint \( a \)--\( b \) paths, contradicting the assumption.

	Let \( a, x_1, \dots, x_\ell, b \) be a shortest \( a \)--\( b \) path.
	Note that \( \ell \geq 2 \) since \( N(a) \cap N(b) = \varnothing \), and in particular, \( x_2 \neq b \).
	Consider \( G - x_1x_2 \).
	We must have that \( \kappa_{a,b}(G - x_1x_2) \leq k - 1 \), otherwise we have a smaller counterexample.
	Hence \( \kappa_{a,b}(G - x_1x_2) = k - 1 \).
	Therefore there is an \( a \)--\( b \) separator \( \widetilde S \) with \( \abs{\widetilde S} = k - 1 \) in \( G - x_1x_2 \).
	We see that either \( \widetilde S \cup \qty{x_1} \) or \( \widetilde S \cup \qty{x_2} \) is a separator of size \( k \) in \( G \), which is not equal to either \( N(a) \) or \( N(b) \).
	Then we can use the above construction to find the relevant contradiction.
\end{proof}
\begin{corollary}[Menger, form 2]
	Let \( G \) be a connected graph with \( \abs{G} \geq 2 \).
	Then \( G \) is \( k \)-connected if and only if all pairs of distinct vertices \( a,b \) admit \( k \) disjoint \( a \)--\( b \) paths.
\end{corollary}
\begin{proof}
	Suppose all pairs of vertices \( a,b \) have \( k \) such paths.
	Suppose \( G - S \) is disconnected, and \( a, b \) lie in different components of \( G - S \).
	Note that \( a \not\sim b \), because there exists a separator for \( a \) and \( b \).
	Then by assumption, there are \( k \) disjoint \( a \)--\( b \) paths, and so \( S \) must intersect each path.
	Therefore, \( \abs{S} \geq k \).

	Now suppose \( G \) is \( k \)-connected.
	Let \( a, b \) be vertices in \( G \).
	If \( a \not\sim b \), apply the first form of Menger's theorem.
	Conversely, consider \( G - ab \).
	This graph is \( k - 1 \)-connected, so there are \( k - 1 \) disjoint \( a \)--\( b \) by Menger's theorem.
	Adding the additional path \( a, b \), we obtain \( k \) disjoint paths as required.
\end{proof}

\subsection{Edge connectivity}
\begin{definition}
	Let \( G \) be a graph.
	Then \( \lambda(G) = \min\qty{\abs{W} \mid W \subseteq E(G), G - W \text{ disconnected}} \) is the smallest amount of edges that can be deleted to disconnect \( G \).
	We say that \( G \) is \emph{\( k \)-edge connected} if \( k \leq \lambda(G) \).
\end{definition}
\begin{example}
	Let \( C_n \) be the cycle on \( n \) vertices.
	The vertex connectivity \( \kappa \) and edge connectivity \( \lambda \) of this graph are both two.
\end{example}
\begin{example}
	Consider a graph with two connected subgraphs \( K_n \), but with one vertex in the intersection between the two.
	Then \( \kappa = 1 \) by deleting the intersection vertex, but \( \lambda(G) = n - 1 \).
\end{example}
\begin{definition}
	Paths \( P_1, \dots, P_k \) are \emph{edge-disjoint} if the edge sets are disjoint.
\end{definition}
\begin{theorem}[Menger, edge version, form 1]
	Let \( G \) be a connected graph, and \( a \neq b \) be vertices.
	Then, if every \( W \subseteq E(G) \) that separates \( a \) from \( b \) has size at least \( k \), then there exist \( k \) edge-disjoint \( a \)--\( b \) paths.
\end{theorem}
\begin{definition}
	Let \( G \) be a graph.
	The \emph{line graph} of \( G \), denoted \( L(G) \), is the graph where \( V(L(G)) = E(G) \) and \( e,f \in E(G) \) are adjacent if they share an endpoint.
\end{definition}
\begin{proof}
	Let \( G' \) be the line graph of \( G \), together with distinguished vertices \( a', b' \) that are connected to the edges incident to \( a \) and \( b \) respectively.
	Note that there is an \( a \)--\( b \) path in \( G \) if and only if there is an \( a' \)--\( b' \) path in \( G' \).
	Thus, \( W \subseteq V(G') \setminus \qty{a',b'} \) is an \( a',b' \) separator if and only if \( W \subseteq E(G) \) separates \( a \) from \( b \).
	Therefore, \( \kappa_{a',b'}(G') \geq k \).
	By the first form of Menger's theorem on \( G' \), we can find \( k \) disjoint \( a' \)--\( b' \) paths \( P_1, \dots, P_k \) in \( G' \).
	These paths describe edge-disjoint \( a \)--\( b \) walks in \( G \), which yield edge-disjoint \( a \)--\( b \) paths.
\end{proof}
\begin{theorem}[Menger, edge version, form 2]
	Let \( G \) be a connected graph.
	Then \( \lambda(G) \geq k \) if and only if all all pairs of vertices \( a \neq b \) admit \( k \) edge-disjoint \( a \)--\( b \) paths.
\end{theorem}
\begin{proof}
	If there exist \( k \) edge-disjoint paths between each pair of vertices, to separate any two vertices we must remove at least one edge from each of these \( k \) paths, so we must remove at least \( k \) edges.
	Conversely, if \( \lambda(G) \geq k \), apply the above form of Menger's theorem.
\end{proof}
